package com.company;

class Solution {

    public static void main(String[] args) {
        // write your code here
        System.out.println("hhh");
    }

    // 1.两数之和
    //https://leetcode-cn.com/problems/two-sum/
    public int[] twoSum(int[] nums, int target) {
        int len = nums.length;
        // 使用哈希表，key存放数值，value存索引
        HashMap<Integer,Integer> hashMap = new HashMap<>(len);
        for (int i = 0; i < len; i ++) {
            if (hashMap.containsKey(target - nums[i])) {
                return new int[] {i, hashMap.get(target - nums[i])};
            }
            hashMap.put(nums[i], i);
        }
        return null;
    }

    // public int[] twoSum(int[] nums, int target) {
    //     int len = nums.length;
    //     for (int i = 0; i < len; i ++) {
    //         for (int j = i + 1; j < len; j++) {
    //             if (nums[i] + nums[j] == target) {
    //                 return new int[] {i,j};
    //             }
    //         }
    //     }
    //     return null;
    // }

    // 4. 寻找两个有序数组的中位数
    // https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int l = m + n;
        double r;
        // if ( l % 2 == 1) {
        //     r = findK( nums1, 0, nums2, 0, (l+1) / 2);
        // } else {
        //     int r1 = findK(nums1, 0, nums2, 0, (l+1)/2);
        //     int r2 = findK(nums1, 0, nums2, 0, (l+2)/2);
        //     r = (r1 + r2) / 2.0f;
        // }

        if (l % 2 == 1) {
            r = findK((l + 1) / 2, nums1, nums2);
        } else {
            int r1 = findK((l + 1) / 2, nums1, nums2);
            int r2 = findK((l + 2) / 2, nums1, nums2);
            // System.out.println("r1 " + r1 + " r2 " + r2);
            r = (r1 + r2) / 2.0f;
        }
        return r;
    }

    int findK(int k, int[] nums1, int[] nums2) {
        int l1 = 0;
        int l2 = 0;
        int r1 = nums1.length;
        int r2 = nums2.length;
        int result = 0;
        do {
            // nums1数组为空
            if (l1 >= r1) {
                result = nums2[l2 + k - 1];
                break;
            }

            // nums2数组为空
            if (l2 >= r2) {
                result = nums1[l1 + k - 1];
                break;
            }

            if (k == 1) {
                result = Math.min(nums1[l1], nums2[l2]);
                break;
            }

            int v1 = l1 + k / 2 - 1 < r1 ? nums1[l1 + k / 2 - 1] : Integer.MAX_VALUE;
            int v2 = l2 + k / 2 - 1 < r2 ? nums2[l2 + k / 2 - 1] : Integer.MAX_VALUE;

            if (v1 < v2) {
                l1 += k / 2;
            } else {
                l2 += k / 2;
            }
            // 这里很重要，不能直接写成 k = k/2
            k = k - k / 2;
        } while (true);
        return result;
    }

    public int findK(int[] nums1, int i, int[] nums2, int j, int k) {
        if (i >= nums1.length)
            return nums2[j + k - 1];
        if (j >= nums2.length)
            return nums1[i + k - 1];
        if (k == 1) {
            return Math.min(nums1[i], nums2[j]);
        }

        int mid1 = (i + k / 2 - 1) < nums1.length ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
        int mid2 = (j + k / 2 - 1) < nums2.length ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
        //通过递归的方式，来模拟删除掉前K/2个元素
        if (mid1 < mid2) {
            return findK(nums1, i + k / 2, nums2, j, k - k / 2);
        }
        return findK(nums1, i, nums2, j + k / 2, k - k / 2);
    }
}